A list is a collection of elements, such as data elements, that are accessed in an explicitly ordered sequential fashion. Common list access operations include the write operation, which receives and stores an element onto the list, and the read operation, which removes and forwards an element from the list. In an environment characterized by multiple thread asynchronous operations, previous list implementations have required that the list be locked for the duration of writing or reading an element. Such operations take an interval of time to complete, and often comprise more than one sequential step. Furthermore, with multiple asynchronous list operations taking place, a new operation may arrive while the sequential steps of a previous operation are in progress. Since the steps of different asynchronous operations are not synchronized, such lists have previously been locked from access by other operations during a list operation to prevent list damage or errors.
In contrast to the conventional approach of locking the list as described above, the lock-free list (LFL) described herein does not need to be locked during multiple asynchronous operations. The invention also may be applied to lock-free queues and lock-free linked lists.
The LFL is a collection of sublists, plus various control means and variables, that inherently protect the list during multiple asynchronous operations without requiring list locking, while provide the same functionality as a single list.
A lock-free list for use with a computer system is provided. The lock-free list comprises a list storage structure comprising at least two sublists, each of a plurality of list elements being sequentially assignable to one of the at least two sublists in such manner that a plurality of assigned list elements is partitionable across the at least two sublists. A plurality of indicators include; an indicator for indicating whether each of the at least two sublists is empty or in use is provided, an indicator for indicating whether a list element is being removed from each of the at least two sublists, an indicator for recording an order of the at least two sublists into which the plurality of assigned list elements are assigned, and an indicator for recording for each of the at least two sublists, a write address location and a read address location.
In order to operate successfully in the environment characterized by multiple thread asynchronous operations involving the list, the invention allows two or more list accesses, including read or write operations, to occur in a time interval of not less than T time units of each other, including the possibility of simultaneous list accesses, such that errors or list corruption do not occur as a result of the time proximity of the list accesses.